The world's technologies for communication, information and entertainment is steadily becoming digital. As part of this trend, still pictures are being stored and transmitted digitally; video is being transmitted and stored in digital form. Digital images and video together constitute an extremely important aspect of modern communication and information infrastructure. Efficient methods for processing multi-dimensional signals such as digital video and images are of deep technological significance. Examples of common application areas where such sophisticated processing is absolutely necessary include image and video compression for efficient video storage and delivery, manipulation of digital images and video frames for effective generation of artificial scenes, image or video restoration etc.
In the context of video compression since a number of the same objects move around in a scene spanning several video frames, one attempts to create shortcuts for describing a current video frame being encoded or compressed in relation to other video frames that have already been transmitted or stored in the bit stream through a process of identification of portions of the current frame w/other portions of previously sent frames. This process is known as motion compensation. As illustrated in FIG. 1A, in technologies such a MPEG 1, 2 and 4, the image frame is subdivided into square blocks that are then matched to a previously encoded frame and a displacement vector, also called motion vector, is placed in the bit stream indicating that the block in question should be replaced by the corresponding block in a previously encoded frame.
Such block-based motion compensation suffers from the limitation that the objects within most images are not built up of blocks. Such an attempt leads to poor matching and motion compensation. In particular blocks that traverse the boundary of two objects tend to have even poorer matches than others. This situation is illustrated in FIG. 1B where block 102 is matched with block 102′ of a previous frame, but block 104 at the boundary of two objects cannot be matched with block 104′. Hence it becomes desirable to be able to directly manipulate the inherent constituent components in any given video frame, which are the objects or parts of objects, segments of arbitrary shapes (as allowed for instance in MPEG4 or as disclosed in Prakash I) as the fundamental entities for use in motion compensation. Any form of motion compensation based on blocks or objects suffers from an additional drawback that as objects move in a video scene, previously occluded regions that constitute new information, appear in the image frame. Such new information in regions that were previously occluded and are now visible, hereafter referred to as exposed area or exposed region, constitute a very large proportion of the encoded information or bit stream in existing video compression technologies. Furthermore, applications such as artificial scene generation based on manipulation of objects or segments that are moved and placed in new locations, also result in such exposed areas. In applications such as image or video restoration where certain parts of an image may be unavailable, lost or corrupted, such regions may also be considered as unknown regions or exposed areas.